package cn.edu.cdu.argorithm.impl;

import cn.edu.cdu.argorithm.IMergeTwoSortedList;
import cn.edu.cdu.argorithm.common.ListNode;

public class MergeTwoSortedList {

    public static class Solution1 implements IMergeTwoSortedList{
        @Override
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            if(list1 == null) {
                return list2;
            }else if(list2 == null) {
                return list1;
            }else if(list1.val <= list2.val) {
                list1.next = mergeTwoLists(list1.next, list2);
                return list1;
            }else {
                list2.next = mergeTwoLists(list1, list2.next);
                return list2;
            }
        }
    }

    public static class Solution2 implements IMergeTwoSortedList{
        @Override
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode dummy = new ListNode();
            ListNode prev = dummy;
            while(list1 != null && list2 != null) {
                if(list1.val <= list2.val) {
                    prev.next = list1;
                    list1 = list1.next;
                } else {
                    prev.next = list2;
                    list2 = list2.next;
                }
                prev = prev.next;
            }
            prev.next = list1 != null ? list1 : list2;
            return dummy.next;
        }
    }
}
